/*
 * Author: Tarl Hahn
 * version: 1.0
 * scheduler
 *
 *
 */
 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 
 #include "global.h"
 #include "process.h"
 #include "scheduler.h"
 
// prototypes
int SchedulerDestruct(SchedulerPtr this);
int SchedulerMax(SchedulerPtr this);
int SchedulerSize(SchedulerPtr this);
char* schedulerToString(SchedulerPtr this, int* error);
char* queuesToString(SchedulerPtr this, int* error);

// select type member functions
ProcessPtr pullRR(SchedulerPtr this, int* error);
ProcessPtr pullNext(SchedulerPtr this, int* error);
ProcessPtr pullNextPriority(SchedulerPtr this, int* error);
ProcessPtr getFromBlocked(SchedulerPtr this, int pid, int blockID, int* error);

// store type member funtions
int pushFCFS(SchedulerPtr this, ProcessPtr process); // first come first serve
int pushPriority(SchedulerPtr this, ProcessPtr process); // priority queue(array)
int pushSTR(SchedulerPtr this, ProcessPtr process); // shortest time remaining ("priority by time" array)

// Blocked queue manipulation functions prototypes
ProcessPtr getProcess(SchedulerPtr this, ProcessPtr tail, int id, int* error);
int addProcess(SchedulerPtr this, ProcessPtr proc, int queue);
 
// construct new scheduler
// size is the max number of processes 
// select_type: How next process is selected. I.E. round robin, next_in_line, 
// store_type: how the processes are stored. I.E. priority, FCFS, Shortest time. 
SchedulerPtr SchedulerConstruct(int size, int select_type, int store_type)
{
	SchedulerPtr scheduler = (SchedulerPtr) malloc(sizeof(Scheduler)); // allocate space for this
	scheduler->array = (ProcessPtr*) malloc(sizeof(ProcessPtr)* size); // allocate space for array
	scheduler->max = size; // set max size
	scheduler->head = 0;
	scheduler->tail = 0;
	scheduler->count = 0;
	scheduler->queueCount = 0;
	scheduler->idle = ProcessConstruct(IDLE, IDLE, IDLE, IDLE, 0, NULL);
	
	// memeber functions
	scheduler->destruct = SchedulerDestruct;
	scheduler->maxProcess = SchedulerMax;
	scheduler->processCount = SchedulerSize;
	scheduler->toString = schedulerToString;
	scheduler->toStringQueues = queuesToString;
	scheduler->proc_Interrupt = getFromBlocked;
	
	// configure next process selection
	switch(select_type)
	{
		case ROUND_ROBIN: // select by round-robin 
			scheduler->nextProcess = pullRR;
			break;
		case PRIORITY: // select by priority.  I.E. priority or STR
			scheduler->nextProcess = pullNextPriority;
			break;
		default: // default is serial programming
			scheduler->nextProcess = pullNext;
	}
	
	// configure process ordering
	switch(store_type)
	{
		case PRIORITY: // maintain priority array
			scheduler->addProcess = pushPriority;
			break;
		case STR: // maintain Shortest time remaining array
			scheduler->addProcess = pushSTR;
			break;
		default: // default first come first serve.
			scheduler->addProcess = pushFCFS;
	}
	return scheduler;
} 
 
// destruct scheduler
int SchedulerDestruct(SchedulerPtr this)
{
	free(this->array);
	free(this);
	return NO_ERROR;
}

// get the next process by getting the next available
ProcessPtr pullNext(SchedulerPtr this, int* error)
{
	// if this is null return error
	if (this == (SchedulerPtr) NULL) 
	{
		*error = NULL_PTR;
		return 0; 
	}
	// if count is zero no elements to return
	if (this->count == 0)
	{
		*error = EMPTY;
		return this->idle;
	}
	this->count--;
	ProcessPtr temp = this->array[this->head];
	// Check process at the beginning of the array to see if it is finished.
	while (temp->num_steps < 1) 
	{	
		// if the head is at the end of the array.
		if (this->head == this->max -1)
		{
			// head is at the end move to the next process at the other end of the queue
			this->head = this->max - this->count; 
		} else
		{
			this->head = this->head + 1; // move head to the next position
		}
		temp = this->array[this->head];
	}
	return temp;
}
 
// get the next process by priority
ProcessPtr pullNextPriority(SchedulerPtr this, int* error)
{
	// if this is null return error
	if (this == (SchedulerPtr) NULL) 
	{
		*error = NULL_PTR;
		return 0; 
	}
	// if count is zero no elements to return
	if (this->count == 0)
	{
		*error = EMPTY;
		return this->idle;
	}
	// Check process at the beginning of the array to see if it is finished.
	if (this->array[0]->num_steps < 1) 
	{
		int head = 1; // set head to point to the left child
		int tail = 0; // set tail to index 0
		while(head < this->count - 1)
		{
			// check priority between the "child nodes" if left is smaller than right
			if (this->array[head]->priority < this->array[head + 1]->priority)
			{
				this->array[tail] = this->array[head]; // move the left child to parent
				tail = head; // update tail
				
			} else // right is smaller then the left
			{
				this->array[tail] = this->array[head + 1]; // move the right child to parent
				tail = head + 1; // update tail
			}
			head = 2 * tail + 1; // update head
		
		}
		this->count = this->count - 1; // reduce count lowest priority process finished.
	}
	return this->array[0]; // return highest priority
}

// get the next process round-robin
ProcessPtr pullRR(SchedulerPtr this, int* error)
{
	// if this is null return error
	if (this == (SchedulerPtr) NULL) 
	{
		*error = NULL_PTR;
		return 0; 
	}
	// if count is zero no elements to return
	if (this->count == 0)
	{
		*error = EMPTY;
		return this->idle;
	}
	// update count and head
	this->count--;
	this->head++; // if head is greater than count or max move head to front of this array
	if (this->head >= this->count || this->head >= this->max) {this->head = 0;}
	
	return this->array[this->head];
} 
 
// add element to the Scheduler
int pushFCFS(SchedulerPtr this, ProcessPtr process)
{
	// check for null pointers
	if(this == (SchedulerPtr) NULL || process == (ProcessPtr) NULL)
	{
		return NULL_PTR;
	}
	int error = 0;
	ProcessPtr temp;
	// if blocked send to the appropriate blocked queue
	switch(process->waiting_on)
	{
		case NETWORK:
		case DISK_IO:
		case VIDEO:
		case KEYBOARD:
		case MOUSE:
			return addProcess(this, process, IO);
		case MUTEX_REQ:
			return addProcess(this, process, MUTEX);
		case CV_REQ:
			return addProcess(this, process, COND_VAR);
		case FREE_IO:
			temp = getProcess(this, this->io, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_MUTEX:
			temp = getProcess(this, this->mutex, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_CV:
			temp = getProcess(this, this->cond, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
	}
	// if count is greater than or equal to max return full.
	if (this->count >= this->max) { return FULL; }
	
	// update count and tail position
	this->count++;
	this->array[this->tail] = process;
	this->tail++; 
	// if tail is greater than or equal to the max move to the front. 
	if(this->tail >= this->max) { this->tail = 0;}
	
	return NO_ERROR;
}

// priority queue(array)
int pushPriority(SchedulerPtr this, ProcessPtr process)
{
	// check for null pointers
	if(this == (SchedulerPtr) NULL || process == (ProcessPtr) NULL)
	{
		return NULL_PTR;
	}
	ProcessPtr temp;
	int error;
	// if blocked send to the appropriate blocked queue
	switch(process->waiting_on)
	{
		case NETWORK:
		case DISK_IO:
		case VIDEO:
		case KEYBOARD:
		case MOUSE:
			return addProcess(this, process, IO);
		case MUTEX_REQ:
			return addProcess(this, process, MUTEX);
		case CV_REQ:
			return addProcess(this, process, COND_VAR);
		case FREE_IO:
			temp = getProcess(this, this->io, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_MUTEX:
			temp = getProcess(this, this->mutex, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_CV:
			temp = getProcess(this, this->cond, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
	}
	
	// if count is greater than or equal to max return full.
	if (this->count >= this->max) { return FULL; }
	// set head and tail pointers
	int head = this->count;
	int tail = this->max;
	
	// add to end of priority array and update count.
	this->array[this->count] = process;
	this->count = this->count + 1;
	// temp var for swapping array elements
	temp = NULL;
	// continue loop till head index = 0.  (higst priority)
	while (head > 0)
	{
		// if head is even
		if(head % 2 == 0)
		{	// use this equation.
			tail = (head - 2) / 2;
		} else 
		{   // head is odd and this equation is used.
			tail = (head - 1) / 2;
		}

		// if the priority of the element at tail index is less than the priority of the element at the head index
		if (this->array[tail]->priority > this->array[head]->priority)
		{
			// swap elements pointed to by head and tail pointers.
			temp = this->array[tail];
			this->array[tail] = this->array[head];
			this->array[head] = temp;
			// update head
			head = tail;
		} else // priority array fixed.
		{   // therefore exit loop.
			break;
		}
	}
	return NO_ERROR;
}

// shortest time remaining ("priority by time" array)
int pushSTR(SchedulerPtr this, ProcessPtr process)
{
	// check for null pointers
	if(this == (SchedulerPtr) NULL || process == (ProcessPtr) NULL)
	{
		return NULL_PTR;
	}
	ProcessPtr temp;
	int error;
	// if blocked send to the appropriate blocked queue
	switch(process->waiting_on)
	{
		case NETWORK:
		case DISK_IO:
		case VIDEO:
		case KEYBOARD:
		case MOUSE:
			return addProcess(this, process, IO);
		case MUTEX_REQ:
			return addProcess(this, process, MUTEX);
		case CV_REQ:
			return addProcess(this, process, COND_VAR);
		case FREE_IO:
			temp = getProcess(this, this->io, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_MUTEX:
			temp = getProcess(this, this->mutex, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
		case FREE_CV:
			temp = getProcess(this, this->cond, process->waiting_on, &error);
			if (error != NOT_FOUND)
			{
				this->addProcess(this, temp);
			}
			break;
	}
	// if count is greater than or equal to max return full.
	if (this->count >= this->max) { return FULL; }
	
	process->priority = process->num_steps; // set priority to the num of steps for the priority queueing
	return pushPriority(this, process); // use pushPriority now that priority matches time remaining in the process.
}

// get the max # of elements the this can contain.
int SchedulerMax(SchedulerPtr this)
{
	// if this is empty return error
	if (this == (SchedulerPtr) NULL) {return NULL_PTR;}
	return this->max; 
}
 
// gets the number of elements
int SchedulerSize(SchedulerPtr this)
{
 	// if this is empty return error
	if (this == (SchedulerPtr) NULL) {return NULL_PTR;}
	return this->count; 
}

// returns a string representation of the scheduler
char* schedulerToString(SchedulerPtr this, int* error)
{	
	// if this is null return error
	if (this == (SchedulerPtr) NULL) 
	{
		*error = NULL_PTR;
		return 0; 
	}
	
	char* string = (char*) malloc(sizeof(char) * this->count * 50);
	strcpy(string, "Scheduler\n");
	int i;
	int index = this->head;
	for(i = 0; i < this->count; i++)
	{
		if(index + i == this->max)
		{
			index = -i;
		}
		strcat(string, this->array[index + i]->toString(this->array[index + i], error));
		strcat(string, "\n");
	}
	
	return string;
}

// returns the specified process from the specified queue
// pid is the process/mutex/condition var ID 
// blockID is the ID associated with why it was blocked... IO, MUTEX, CONDITION_VAR
// error is the pointer returning the error code
ProcessPtr getFromBlocked(SchedulerPtr this, int id, int blockID, int* error)
{
	// if this is null return error
	if (this == (SchedulerPtr) NULL) 
	{
		*error = NULL_PTR;
		return 0; 
	}

	ProcessPtr head;
	switch (blockID)
	{
		case IO:	// use IO queue
			head = this->io; // get head pointer
			// test head pointer for match
			if(this->io->waiting_on == id)
			{	// update head pointer and return tail.
				this->io = this->io->next;
				head->waiting_on = NOT_WAITING;
				return head;
			}
			
			break;
			
		case MUTEX_BLOCK: // use mutex queue
			head = this->mutex;
			// test head pointer for match
			if(this->mutex->waiting_on == id)
			{	// update head pointer and return head.
				this->mutex = this->mutex->next;
				head->waiting_on = NOT_WAITING; // update waiting field
				return head;
			}
			break;
			
		case COND_VAR: // use condition var queue
			head = this->cond;
			// test head pointer for match
			if(this->cond->waiting_on == id)
			{	// update head pointer and return tail.
				this->cond = this->cond->next;
				head->waiting_on = NOT_WAITING; // update waiting field
				return head;
			}
			break;
			
		default: // default is an INVALID_BLOCK_ID... should never ever happen
			*error = INVALID_BLOCK_ID;
			return NULL;
	}
	head = getProcess(this, head, id, error);
	return head;
}

// Gets the process from the queue using the specified params
// proc is the process being added.
// queue is the name of the queue being added to
// id is the process/mutex/condition var id 
ProcessPtr getProcess(SchedulerPtr this, ProcessPtr tail, int id, int* error)
{	// If the io queue is empty update error and return null
	if (tail == (ProcessPtr) NULL)
	{
		*error = EMPTY;
		return NULL;
	} 
	// set up head iterator
	ProcessPtr head = tail->next;
	// setup error in hopes it will be found.
	*error = NO_ERROR;			
	// loop thru the queue to find the process 
	while (head != (ProcessPtr) NULL)
	{	// if the id's match set up for return with no error
		// fix queue 
		if(head->waiting_on == id)
		{ 	// update linked list and return head
			tail->next = head->next;
			this->queueCount--;
			return head;
		} // update iterraters process not found yet
		head = head->next;
		tail = tail->next;
	}
	
	// NOT FOUND update error and RETURN NULL
	*error = NOT_FOUND; 
	return NULL;
}

// Adds the process from the queue using the specified params
// proc is the process being added.
// queue is the name of the queue being added to
// pid is the process/mutex/condition var id 
int addProcess(SchedulerPtr this, ProcessPtr proc, int queue)
{	
	ProcessPtr iter; // create iterator 
	switch(queue) 	 // switch to assign iterator to proper queue.
	{
		case IO:	// io queue
			if(this->io == (ProcessPtr) NULL) 
			{ 
				this->io = proc;
				return NO_ERROR;
			}
			iter = this->io;
			break;
		case MUTEX:	// mutex queue
			if(this->mutex == (ProcessPtr) NULL) 
			{ 
				this->mutex = proc;
				return NO_ERROR;
			}
			iter = this->mutex;
			break;
		case COND_VAR:	// condition_var queue
			if(this->cond == (ProcessPtr) NULL) 
			{ 
				this->cond = proc;
				return NO_ERROR;
			}
			iter = this->cond;
			break;
		default:
			return INVALID_BLOCK_ID;
	}
	 
	// move iter to the end of the list
	while(iter->next != (ProcessPtr) NULL) { iter = iter->next; }
	iter->next = proc; 		// assign proc to the end
	proc->next = NULL;  // make sure proc-> next is null.
	this->queueCount++;
	return NO_ERROR;
}

// counts the queue
int countQueue(ProcessPtr proc)
{
	ProcessPtr iter = proc;
	int count = 0; // length of queue
	// get length of the queue assign to count
	while(iter != (ProcessPtr) NULL) 
	{ 
		count++;  // update count
		iter = iter->next; // move iter to the next process
	}
	return count;
}
//
char* queuesToString(SchedulerPtr this, int* error)
{
	if(this == (SchedulerPtr) NULL)
	{
		*error = NULL_PTR;
		return 0;
	}
	// initialize strings
	char* string = (char*) malloc(sizeof(char) * this->queueCount * 100 + 4);
	char* process = (char*) malloc(sizeof(char) * 20);
	
	IOtoString(this->io, string, process); 			// IO queue To String
	
	MUTEXtoString(this->mutex, string, process, "M", countQueue(this->mutex));	// MUTEX queue to string
	
	CVtoString(this->cond, string, process, "CV", countQueue(this->cond));		// Condition Var queue to string
	// trim and return string.
	return strtok (string,""); 
}

int IOtoString(ProcessPtr iter, char* destination, char* proc_str)
{
	strcpy(destination, "IO: ");
	while(iter != (ProcessPtr) NULL)
	{	// get string rep of process
		snprintf(proc_str, 10, "P%d, ", iter->pid); 
		strcat(destination, proc_str);
		iter = iter->next;
	}
	strcat(destination, "\n");
}

// converts both mutexes and condition vars to strings.
int MUTEXtoString(ProcessPtr queue, char* destination, char* proc_str, char* header, int count)
{
	if(queue == (ProcessPtr) NULL)
	{
		return EMPTY;
	}
	// initialize head pointer
	ProcessPtr iter = queue;
	int waiting_on = 0;
	int i;
	// loop thru list
	strcat(destination, "Mutex: ");
	while(iter != (ProcessPtr) NULL)
	{
		// Get the header for the queue list
		snprintf(proc_str, 20, "P%d waiting %s%d, ", iter->pid, header, iter->waiting_on); 
		strcat(destination, proc_str); // add it to the main string
		iter = iter->next; // update head iter
	}
		
	strcat(destination, "\n");
	return NO_ERROR;
}

// condition variable queue to string
int CVtoString(ProcessPtr queue, char* destination, char* proc_str, char* header, int count)
{
	if(queue == (ProcessPtr) NULL)
	{
		return EMPTY;
	}
	// initialize head pointer
	ProcessPtr iter = queue;
	int waiting_on = 0;
	int i;
	// loop thru list
	strcat(destination, "CV: ");
	while(iter != (ProcessPtr) NULL)
	{
		// Get the header for the queue list
		snprintf(proc_str, 22, "P%d waiting on %s%d, ", iter->pid, header, iter->waiting_on); 
		strcat(destination, proc_str); // add it to the main string
		iter = iter->next; // update head iter
	}
		
	strcat(destination, "\n");
	return NO_ERROR;
}

/*
int main(void)
{
	int error = 0;
	SchedulerPtr this = SchedulerConstruct(100, PRIORITY, PRIORITY);
	int requests[] = {NETWORK, KEYBOARD};
	ProcessPtr test;
	int i;
	for(i = 0; i < 10; i++)
	{
		// created the process to add to the scheduler
		test = ProcessConstruct(i, 10-i, IO, i, 2, &requests[0], NULL);
		this->addProcess(this,test);
		test->waiting_on = COND_VAR;
	}
	// print the process list
	printf(this->toStringQueues(this, &error));
	getchar();
	
	
	// remove all EMPTY TEST
	for(i = 0; i < 10; i++)
	{
		test = this->nextProcess(this, &error);
		this->addProcess(this, test);
	}
	// print the process list
	printf("Empty Test\n");
	printf(this->toString(this, &error));
} */
